// https://leetcode.cn/problems/find-duplicate-subtrees/
// Created by ade on 2022/9/5.
// 给定一棵二叉树 root，返回所有重复的子树。
//
//对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
//
//如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
//
// 输入：root = [1,2,3,4,null,2,4,null,null,4]
// 输出：[[2,4],[4]]
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 对比两个二叉树是否相等
    // 思路：
    unordered_map<string, int> m = {};
    vector<TreeNode *> res = {};

    vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
        dfs(root);
        return res;
    }

    string dfs(TreeNode *node) {
        if (!node) return "";
        string s = to_string(node->val) + " " + dfs(node->left) + " " + dfs(node->right);
        m[s]++;
        if (m[s] == 2) res.push_back(node);
        return s;
    }

    TreeNode *init() {
        TreeNode *h1 = new TreeNode(5);
        TreeNode *h2 = new TreeNode(5);
        TreeNode *h3 = new TreeNode(5);
        TreeNode *h4 = new TreeNode(1);
        TreeNode *h5 = new TreeNode(4);
        TreeNode *h6 = new TreeNode(1);
        h1->left = h5;
        h1->right = h2;
        h5->left = h4;
        h5->right = h6;
        h2->right = h3;

        return h1;
    }
};

int main() {
    Solution so;
    TreeNode *h = so.init();
    so.findDuplicateSubtrees(h);
    return 0;
}